// easy

// 假设你正在爬楼梯，需要n阶才能到达楼顶，每次你可以爬1或2个台阶，现在给定一个整数n
// 要求计算出有多少种不同的方法可以爬到楼顶

// 解题思路：动态规划
// 1. 划分阶段：按照台阶的层数进行划分0-n
// 2. 定义状态，状态dp[i]表示爬到第i阶台阶的方案数
// 3. 状态转移方程
// 每次只能爬1或2个台阶，则第i阶楼梯只能从第i-1阶爬1阶上来，或者从第i-2阶向上爬2阶上来，所以可以推出状态转移方程为
// dp[i] = dp[i-1] + dp[i-2]
// 4. 初始条件
//      1. 第0层台阶方案数：dp[0] = 1,可以看做是1中方法，从0阶上爬0阶
//      2. 第1层台阶方案数：dp[1] = 1
//      3. 第2层台阶方案数：dp[2] = 2
// 5. 最终结果，dp[n]

// 复杂度分析
// 时间复杂度：O(n)
// 空间复杂度：O(n)

function climbStairs(n) {
    let dp = new Array(n + 1).fill(0)
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i < n + 1; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}

let n = 3
console.log(climbStairs(n))